/*
 * Saphre - Suffix Arrays for Phrase Extraction
 * Copyright (C) 2013 
 * Dale Gerdemann - Tübingen, Germany 
 * Niko Schenk - Frankfurt am Main, Germany
 * All rights reserved.
 *
 * This program is free software: you can redistribute it and/or modify it under
 * the terms of the GNU General Public License as published by the Free Software
 * Foundation, either version 3 of the License, or (at your option) any later
 * version.
 *
 * This program is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
 * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
 * details.
 *
 * You should have received a copy of the GNU General Public License along with
 * this program. If not, see <http://www.gnu.org/licenses/>.
 *
 */
package util;

import java.util.*;

/*
 * Originally from Sedgewick and Wayne, with modification to use
 * util.IntString. Changed generic Value to primitive type int with
 * value -1 playing the role of null. This is ok for our purposes: a
 * state is never labeled -1.
 * 
 * @author Dale Gerdemann
 */
public class IntTST {

    private boolean epsilon = false; // addition to handle empty string
    private int epsilonVal;
    private int N;       // size
    private Node root;   // root of IntTST

    private class Node {

        private int c;                 // character
        private Node left, mid, right;  // left, middle, and right subtries
        private int val;              // value associated with string
    }

    // return number of key-value pairs
    public int size() {
        return N;
    }

    /**
     * ***********************************************************
     * Is string key in the symbol table?
     * ************************************************************
     */
    public boolean contains(int[] key) {
        if (key.length == 0) {
            return epsilon;
        }
        IntString s = new IntString(key);
        return contains(s);
    }

    public boolean contains(IntString key) {
        if (key.length() == 0) {
            return epsilon;
        }
        return get(key) != -1;
    }

    public int get(IntString key) {
        if (key.length() == 0) {
            return epsilonVal;
        }
        if (key == null || key.length() == 0) {
            throw new RuntimeException("illegal key");
        }
        Node x = get(root, key, 0);
        if (x == null) {
            return -1;
        }
        return x.val;
    }

    // return subtrie corresponding to given key
    private Node get(Node x, IntString key, int d) {
        if (key == null || key.length() == 0) {
            throw new RuntimeException("illegal key");
        }
        if (x == null) {
            return null;
        }
        int c = key.charAt(d);
        if (c < x.c) {
            return get(x.left, key, d);
        } else if (c > x.c) {
            return get(x.right, key, d);
        } else if (d < key.length() - 1) {
            return get(x.mid, key, d + 1);
        } else {
            return x;
        }
    }

    /**
     * ***********************************************************
     * Insert string s into the symbol table.
     * ************************************************************
     */
    public void put(int[] s) {
        if (s.length == 0) {
            epsilon = true;
            return;
        }
        IntString key = new IntString(s);
        put(key);
    }

    public void put(IntString s) {
        if (s.length() == 0) {
            epsilonVal = 0;
            return;
        }
        put(s, 0);
    }

    public void put(IntString s, int val) {
        if (s.length() == 0) {
            epsilonVal = val;
            return;
        }
        if (!contains(s)) {
            N++;
        }
        root = put(root, s, val, 0);
        keys();

    }

    private Node put(Node x, IntString s, int val, int d) {
        int c = s.charAt(d);
        if (x == null) {
            x = new Node();
            x.c = c;
            x.val = -1;
        }
        if (c < x.c) {
            x.left = put(x.left, s, val, d);
        } else if (c > x.c) {
            x.right = put(x.right, s, val, d);
        } else if (d < s.length() - 1) {
            x.mid = put(x.mid, s, val, d + 1);
        } else {
            x.val = val;
        }
        return x;
    }

    /**
     * ***********************************************************
     * Find and return longest prefix of s in IntTST
     * ************************************************************
     */
    public IntString longestPrefixOf(IntString s) {
        if (s == null || s.length() == 0) {
            return null;
        }
        int length = 0;
        Node x = root;
        int i = 0;
        while (x != null && i < s.length()) {
            int c = s.charAt(i);
            if (c < x.c) {
                x = x.left;
            } else if (c > x.c) {
                x = x.right;
            } else {
                i++;
                if (x.val != -1) {
                    length = i;
                }
                x = x.mid;
            }
        }
        return s.substring(0, length);
    }

    // all keys in symbol table
    public Iterable<IntString> keys() {
        IntString prefix = IntString.EMPTY;
        Queue<IntString> queue = new LinkedList<IntString>();
        if (root == null) {
            return queue;
        }
        collect(root.left, prefix, queue);
        IntString extended = prefix.plus(root.c);
        if (root.val != -1) {
            queue.add(extended);
        }
        collect(root.mid, extended, queue);
        collect(root.right, prefix, queue);
        return queue;
    }

    // all keys starting with given prefix
    public Iterable<IntString> prefixMatch(IntString prefix) {
        Queue<IntString> queue = new LinkedList<IntString>();
        Node x = get(root, prefix, 0);
        if (x.val != -1) {
            queue.add(prefix);
        }
        collect(x.mid, prefix, queue);
        return queue;
    }

    // all keys in subtrie rooted at x with given prefix
    private void collect(Node x, IntString prefix, Queue<IntString> queue) {
        if (x == null) {
            return;
        }
        collect(x.left, prefix, queue);
        if (x.val != -1) {
            queue.add(prefix.plus(x.c));
        }
        collect(x.mid, prefix.plus(x.c), queue);
        collect(x.right, prefix, queue);
    }

    // return all keys matching given wilcard pattern
    public Iterable<IntString> wildcardMatch(IntString pat) {
        Queue<IntString> q = new LinkedList<IntString>();
        collect(root, IntString.EMPTY, 0, pat, q);
        return q;
    }

    public void collect(Node x, IntString prefix, int i, IntString pat, Queue<IntString> q) {
        if (x == null) {
            return;
        }
        int c = pat.charAt(i);
        if (c == '.' || c < x.c) {
            collect(x.left, prefix, i, pat, q);
        }
        if (c == '.' || c == x.c) {
            if (i == pat.length() - 1 && x.val != -1) {
                q.add(prefix.plus(x.c));
            }
            if (i < pat.length() - 1) {
                collect(x.mid, prefix.plus(x.c), i + 1, pat, q);
            }
        }
        if (c == '.' || c > x.c) {
            collect(x.right, prefix, i, pat, q);
        }
    }

    /**
     * Test client.
     * @param args 
     */
    public static void main(String[] args) {
        // build symbol table from standard input
        IntTST st = new IntTST();
        int[] f1 = {1, 3, 5};
        int[] f2 = {1, 4, 6};

        IntString is1 = new IntString(f1);
        IntString is2 = new IntString(f2);

        st.put(is1);
        st.put(is2);

        for (IntString is : st.keys()) {
            System.out.println(is);
        }
    }
}
